package _07_priority_queue.my_implements;

import _04_queue.AbstractQueue;
import _07_priority_queue.Priority;

import java.util.Iterator;

/**
 * @author: mornd
 * @dateTime: 2023/6/8 - 3:09
 * 基于有序数组实现优先级队列（插入时需要按顺序插入）
 * 适用于出队操作多于入队的场景
 * O(n)
 */
public class PriorityQueue2<E extends Priority> extends AbstractQueue<Priority> {
    Priority data[];
    int size;
    int capacity;

    public PriorityQueue2(int capacity) {
        this.capacity = capacity;
        data = new Priority[this.capacity];
    }

    /**
     * 插入排序实现
     *
     * @param p 插入的元素
     * @return
     */
    @Override
    public boolean offer(Priority p) {
        if (isFull()) {
            return false;
        }
        insert(p);
        size++;
        return true;
    }

    /**
     * 时间复杂度 O(n)
     * 找到指定位置插入元素 p
     * @param p
     */
    private void insert(Priority p) {
        /*
         保证数组最少有一个空位

         0,1,2,3,null

         每次新增时，p和前面对比，如果比前面小则p向前插入
         */
        int i = size - 1;
        for (; i >= 0 && data[i].priority() > p.priority(); i--) {
            data[i + 1] = data[i];
        }
        data[i + 1] = p;
    }

    /**
     * 时间复杂度 O(1)
     * 直接出队即可
     * @return
     */
    @Override
    public Priority poll() {
        if (isEmpty()) {
            return null;
        }
        return data[--size];
    }

    @Override
    public Priority peek() {
        if (isEmpty()) {
            return null;
        }
        return data[size - 1];
    }

//    @Override
//    public boolean isEmpty() {
//        return size == 0;
//    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<Priority> iterator() {
        return new Iterator<Priority>() {
            int p = size;

            @Override
            public boolean hasNext() {
                return p > 0;
            }

            @Override
            public Priority next() {
                return data[--p];
            }
        };
    }
}
